Problem statement: zenit15cki

Izbové rybičky vs. akvárium

Počet bodov: 40, časový limit: 1500ms

Miška si jedného pekného dňa zaumienila, že chce rybičky. Zohnala si akvárium, výživnú pôdu pre rastlinky, piesok a štrk¹, ovzdušnovač, vodný filter a ohrievač vody. Potom akvárium vyčistila, vystlala výživnou pôdou, nasypala vrstvu piesku a štrku. Nakoniec napustila vodu, povkladala (a otestovala) všetky zariadenia. Všetko vyzeralo pekne, funkčne a útulne, tak si zaobstarala rybičky aj s krmivom a nejakými tými rastlinkami.

A vtedy nastali problémy. Rybičky nechcú jesť, schovávajú sa pod filter, aj pod ovzdušňovač. Miška sa teda rozhodla veľmi rýchlo situáciu vyriešiť tým, že im pozháňa rôzne väčšie dekorácie, do ktorých by sa mohli rybičky poschovávať. Nabehla teda rýchlo do obchodu a nakúpila, čo jej do očí padlo.

Keď však prišla domov, čakal ju veľmi nemilý pohľad. Rybičky si začali úkryty robiť po svojom. To konkrétne robili tak, že sa zavŕtavali do pôdy². Tam, kde sa zavŕtali, ostala diera, všetok materiál sa rozvíril vo vode a väčšina sa časom usadila v celom zvyšku akvária (v diere nie), niečo sa zachytilo vo filtri.

Miška z toho ostala nešťastná, lebo teraz nevie, kam má umiestniť poskupované dekorácie tak, aby sa na rybičky nezošuchli. Vždy si vytipuje nejakú pekne vyzerajúcu oblasť a v nej umiestni ďalší kus do najnižšie položeného miesta.

Rybičky sú stále aktívne a Miška vie umiestňovať rôzne kusy výbavy len po jednej, preto potrebuje od vás, aby ste jej vždy, keď to bude potrebovať, zistili, ako hlboko je najnižšie práve položené miesto v jej vytipovanej oblasti. Už položené predmety nijako neovplyvňujú, ako sa rybičky, prípadne podložie, správajú. Dokonca chce občas Miška položiť ďalší predmet tam, kde už nejaký je.

Úloha

Na akvárium sa budeme pozerať zhora. Pri takomto pohľade si ho budeme reprezentovať ako mriežku rozmerov \(r \times s\). Súradnice budeme číslovať od \(0\). (Teda napr. riadky majú postupne zhora dole čísla 0 až \(r-1\).) Ďalej sa budú diať udalosti dvoch typov:

• Ryby vyhrabali jedno políčko v \(a\)-tom riadku a \(b\)-tom stĺpci. V tomto políčku klesla hladina podložia o \(x\), zatiaľčo v celom zvyšku akvária stúpla úroveň podložia o \(y\).
• Miška ide umiestňovať ďalší kus rybieho nábytku a potrebuje vedieť, aké najnižšie políčko sa nachádza v obdĺžnikovej oblasti s ľavým horným rohom v riadku \(a\) a stĺpci \(b\) a s pravým dolným rohom v riadku \(c\) a stĺpci \(d\) vrátane. Nezaujíma ju, ktoré políčko má túto výšku, zaujíma ju len, aké vysoké je podložie v tomto políčku.

Po každej udalosti druhého typu vypíšte na samostatný riadok jedno číslo – výšku podložia v najnižšom políčku zo zadanej oblasti.

Vstup a výstup

Na prvom riadku vstupu budú čísla \(r\), \(s\), \(f\) a \(q\) (\(1 \leq r, s \leq 4000\), \(1 \leq f, q \leq 100\,000\)), počet riadkov a stĺpcov akvária pri pohľade zhora, pôvodnú výšku podložia v akváriu a počet udalostí v akváriu.

Nasleduje \(q\) riadkov, každý popisujúci jednu udalosť. Pokiaľ ide o udalosť prvého typu, čiže rybie tunelovanie, v tomto riadku budú v takomto poradí celé čísla \(1\), \(a\), \(b\), \(x\), \(y\), pokiaľ o udalosť druhého typu, v riadku budú v takomto poradí celé čísla \(2\), \(a\), \(b\), \(c\), \(d\).

Môžete predpokladať, že pre každú udalosť platí \(a \leq c\), \(b \leq d\), všetky zadané súradnice budú vnútri akvária, \(x\) a \(y\) budú čísla od \(0\) do \(1000\).

Výška každého políčka v každom momente musí ostať nezáporná. Ak by mala výška nejakého políčka klesnúť do záporných čísel, ostane namiesto toho nulová (číslom: \(0\)). Ak teda nejaké políčko má výšku \(1\), klesne o \(1000\) a potom narastie o \(999\), jeho výška na konci bude \(999\).

Aspoň 28 bodov však môžete získať za riešenie, ktoré predpokladá, že žiadne políčko v žiadnom momente nebude chcieť klesnúť na zápornú výšku.

Príklad

Input:

11 19 10 7
2 1 1 4 4
1 4 4 1 1
2 3 1 6 4
1 1 8 5 2
2 1 1 10 10
2 4 4 5 5
2 9 9 10 18

Output:

10
9
6
11
13

Stavy akvária v čase prvých troch udalostí typu 2 (hľadanie minima v nejakej oblasti).

Na obrázku, ktorý sa nachádza na stránke, môžete vidieť priebeh toho, ako sa menila úroveň podložia.